package org.czl.leetcode4;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class l399 {
    public static void main(String[] args) {
        List<List<String>> list = new ArrayList<>();
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("a");
        list1.add("b");
        ArrayList<String> list2 = new ArrayList<>();
        list2.add("b");
        list2.add("c");
        list.add(list1);
        list.add(list2);

        List<List<String>> query = new ArrayList<>();
        ArrayList<String> query1 = new ArrayList<>();
        query1.add("a");
        query1.add("c");
        ArrayList<String> query2 = new ArrayList<>();
        query2.add("b");
        query2.add("a");
        query.add(query1);
        query.add(query2);
        System.out.println(Arrays.toString(calcEquation(list, new double[]{2.0, 3.0}, query)));
    }
    //带权并查集做法
    static HashMap<String, String> father = new HashMap<>();
    static HashMap<String, Double> dist = new HashMap<>();
    public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries){
        //初始化并查集
        for(List<String> list : equations){
            for(String s : list){
                father.put(s, s);
                dist.put(s, 1.0);
            }
        }
        int index = 0;
        for(List<String> list : equations){
            union(list.get(0), list.get(1), values[index++]);
        }
        double[] ans = new double[queries.size()];
        index = 0;
        for(List<String> list : queries){
            String s1 = find(list.get(0));
            String s2 = find(list.get(1));
            if(s1 != null && s2 != null && s1.equals(s2)){
                ans[index++] = dist.get(list.get(0)) / dist.get(list.get(1));
            }else{
                ans[index++] = -1.0;
            }
        }
        return ans;
    }
    static void union(String s1, String s2, double val){
        String str1 = find(s1); String str2 = find(s2);
        if(!str1.equals(str2)){
            father.put(str1, str2);
            dist.put(str1, dist.get(s2) / dist.get(s1) * val);
        }
    }
    static String find(String s){
        if(!father.containsKey(s))return null;
        if(!father.get(s).equals(s)){
            String tmp = father.get(s);
            String fa = find(father.get(s));
            dist.put(s, dist.get(s) * dist.get(tmp));
            father.put(s, fa);
        }
        return father.get(s);
    }
}
